import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定一组正整数数组 M，找出 M 数组中 N 项和为给定数 S。如果有多对 N 项数字的和都等于 S，则输出 N 个数的乘
 * 积最小的哪一项，没有则返回空；
 */


public class Solution {
    static List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
    static LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
    public static void main(String[] args) {
        int[] M = {3,2,6,4};
        int N = 2;
        int S = 5;
        if(N>M.length) {
            System.out.println("输出NULL");
        }
        //对M数组排序
        choiceSort(M);
        if(S<M[0]){
            System.out.println("输出NULL");
        }

        subsetsHelper(M, 0);
        int[][] res = new int[100][N];
        //val记录最小的N个数的乘积
        int val = Integer.MAX_VALUE;
        int index=0;
        for (int i = 0; i < result.size(); i++) {
            if(result.get(i).size()==N){
                for (int j = 0; j < result.get(i).size(); j++) {
                    res[index][j]=result.get(i).get(j);
                }
                index++;
            }
        }
        boolean flag = true;
        boolean fla = true;
        int value =0;
        for (int i = 0; i < index; i++) {
            int sum = 1;
            value = 0;
            for (int j = 0; j < N; j++) {
                sum *= res[i][j];
                value += res[i][j];
            }
            if (value == S) {
                if (flag == true) {
                    flag = false;
                    val = Math.min(val, sum);
                } else if (flag == false) {
                    fla = false;
                    val = Math.min(val, sum);
                }
            }
        }
        if(fla==true&&flag==true){
            System.out.println("没有对应数组，返回空");
        }else if(fla==true){
            System.out.println("N 项数字的和"+value);
        }else if(fla==false&&flag==false){
            System.out.println("N 项数字的乘积"+value);
        }

    }

    private static void choiceSort(int[] num) {

        for (int i = 0; i < num.length; i++) {
            for (int j = i+1; j < num.length; j++) {
                if(num[i]>num[j]){
                    swap(num,i,j);
                }
            }
        }
    }
    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void subsetsHelper(int[] nums, int startIndex){
        result.add(new ArrayList<>(path));//遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合。
        if (startIndex >= nums.length){ //终止条件
            return;
        }
        for (int i = startIndex; i < nums.length; i++){
            path.add(nums[i]);
            subsetsHelper(nums, i + 1);
            path.removeLast();
        }
    }
}